{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Rank Transform of an Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: arrayRankTransform"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组序号转换"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>arr</code> ，请你将数组中的每个元素替换为它们排序后的序号。</p>\n",
    "\n",
    "<p>序号代表了一个元素有多大。序号编号的规则如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>序号从 1 开始编号。</li>\n",
    "\t<li>一个元素越大，那么序号越大。如果两个元素相等，那么它们的序号相同。</li>\n",
    "\t<li>每个数字的序号都应该尽可能地小。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [40,10,20,30]\n",
    "<strong>输出：</strong>[4,1,2,3]\n",
    "<strong>解释：</strong>40 是最大的元素。 10 是最小的元素。 20 是第二小的数字。 30 是第三小的数字。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [100,100,100]\n",
    "<strong>输出：</strong>[1,1,1]\n",
    "<strong>解释：</strong>所有元素有相同的序号。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [37,12,28,9,100,56,80,5,12]\n",
    "<strong>输出：</strong>[5,3,4,2,8,6,7,1,3]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= arr.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup>&nbsp;&lt;= arr[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [rank-transform-of-an-array](https://leetcode.cn/problems/rank-transform-of-an-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [rank-transform-of-an-array](https://leetcode.cn/problems/rank-transform-of-an-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[40,10,20,30]', '[100,100,100]', '[37,12,28,9,100,56,80,5,12]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        new_arr = sorted(list(set(arr)))\n",
    "        for num in arr:\n",
    "            pos = bisect_left(new_arr, num)\n",
    "            ans.append(pos + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        s=sorted(set(arr))\n",
    "        ans=[]\n",
    "        for num in arr:\n",
    "            ans.append(bisect.bisect_left(s,num)+1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr):\n",
    "        n = len(arr)\n",
    "        index = sorted(range(n), key=lambda i: arr[i])\n",
    "        cnt = 0\n",
    "        temp = None\n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            tar = index[i]\n",
    "            if temp == arr[tar]:\n",
    "                cnt += 1\n",
    "            temp = arr[tar]\n",
    "            ans[tar] = i + 1 - cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        idxes = [i for i in range(len(arr))]\n",
    "        idxes.sort(key = lambda x : arr[x])\n",
    "        ans = [0] * (len(arr))\n",
    "        order = 0\n",
    "        for i in range(0, len(arr)):\n",
    "            if i == 0 or arr[idxes[i]] != arr[idxes[i - 1]]:\n",
    "                order += 1\n",
    "            ans[idxes[i]] = order\n",
    "        return ans            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        s = set(arr)\n",
    "        l = list(s)\n",
    "        l.sort()\n",
    "        return [bisect.bisect_left(l, n) + 1 for n in arr]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        if n == 0:\n",
    "            return []\n",
    "        a1 = sorted(list(range(n)), key=lambda i:arr[i])\n",
    "        res = [0] * n\n",
    "        res[a1[0]] = 1\n",
    "        pre = arr[a1[0]]\n",
    "        idx = 1\n",
    "        for i in range(1, n):\n",
    "            j = a1[i]\n",
    "            if arr[j] != pre:\n",
    "                idx += 1\n",
    "            res[j] = idx\n",
    "            pre = arr[j]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedDict\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        map = SortedDict()\n",
    "        for i in arr:\n",
    "            map[i] = 0\n",
    "        index = 1\n",
    "        for key in map.keys():\n",
    "            map[key] = index\n",
    "            index += 1\n",
    "        for i in range(len(arr)):\n",
    "            arr[i] = map[arr[i]]\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        _set = SortedSet(arr)\n",
    "        res = []\n",
    "        for num in arr:\n",
    "            res.append(_set.index(num) + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        _set = SortedSet(arr)\n",
    "        res = []\n",
    "        for num in arr:\n",
    "            res.append(_set.index(num) + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        hashmap=Counter(arr)\n",
    "        mylist=list(hashmap.keys())\n",
    "        mylist.sort()\n",
    "        # mylist=sorted(set(arr))\n",
    "        # hashmap={}\n",
    "        for i, n in enumerate(mylist,1):\n",
    "            hashmap[n]=i\n",
    "        return [hashmap[n] for n in arr]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        length = len(arr)\n",
    "        numDict = defaultdict(int)\n",
    "        for v in arr:\n",
    "            numDict[v] = 1\n",
    "        keys = list(numDict.keys()) \n",
    "        keys.sort()\n",
    "        for i in range(len(keys)):\n",
    "            numDict[keys[i]] = i+1\n",
    "        \n",
    "        res = [0 for _ in range(length)]\n",
    "        \n",
    "        for i in range(length):\n",
    "            res[i] = numDict[arr[i]]\n",
    "        \n",
    "        # for i in range(len)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        index = [i for i in range(len(arr))]\n",
    "        index.sort(key=lambda x:arr[x])\n",
    "        ind = 1\n",
    "        res = [1]*len(arr)\n",
    "        for i in range(1,len(index)):\n",
    "            if arr[index[i]]!=arr[index[i-1]]:\n",
    "                ind+=1\n",
    "            res[index[i]]=ind\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cmp_to_key\n",
    "\n",
    "class Solution: \n",
    "\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]: \n",
    "        idxes = list(range(len(arr))) \n",
    "        idxes.sort(key=cmp_to_key(lambda a, b: arr[a] - arr[b]))\n",
    "        n = len(idxes)\n",
    "        rank_id = 1  \n",
    "        for i in range(n):\n",
    "            # 排在第i位的是arr[idx]\n",
    "            idx = idxes[i] \n",
    "            next_idx = idxes[i + 1] if i < n - 1 else None \n",
    "            if next_idx is not None and arr[next_idx] != arr[idx]:\n",
    "                arr[idx] = rank_id \n",
    "                rank_id += 1 \n",
    "            else:\n",
    "                arr[idx] = rank_id \n",
    "        return arr \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        numDict = {}\n",
    "        for num in arr:\n",
    "            numDict[num] = -1\n",
    "        \n",
    "        bakArr = arr[:]\n",
    "        \n",
    "        arr = list(numDict.keys())\n",
    "        arr.sort()\n",
    "               \n",
    "        for i in range(len(arr)):           \n",
    "            numDict[arr[i]] = i+1\n",
    "            \n",
    "        res = []\n",
    "        for num in bakArr:\n",
    "            res.append(numDict[num])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        m = {}\n",
    "        for i in arr:\n",
    "            m[i] = 0\n",
    "\n",
    "        order = sorted(m.keys(), key=lambda x: x)\n",
    "        idx = 1\n",
    "        for i in order:\n",
    "            m[i] = idx\n",
    "            idx += 1\n",
    "\n",
    "        for a in range(len(arr)):\n",
    "            arr[a] = m[arr[a]]\n",
    "\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        \n",
    "        temp = sorted(arr)\n",
    "        \n",
    "        dic = {}\n",
    "        index = 0\n",
    "        for num in temp:\n",
    "            if num in dic:\n",
    "                continue\n",
    "            else:\n",
    "                dic[num] = index+1\n",
    "                index+=1\n",
    "        \n",
    "        return list(map(lambda x:dic[x],arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 方法一：排序+哈希表\n",
    "# 第一步：数组排序order\n",
    "# 第二步：将排好序的数组和其大小排名加入字典rank中\n",
    "# 第三步：遍历数组，然后返回其在字典中的值即其大小排名\n",
    "# class Solution:\n",
    "#     def arrayRankTransform(self, arr):\n",
    "#         order = sorted(list(set(arr)))\n",
    "#         rank = {x: i+1 for i, x in enumerate(order)}\n",
    "#         return [rank[x] for x in arr]\n",
    "\n",
    "\n",
    "# 方法二：小顶堆\n",
    "# 第一步：将元素和其下标(x,i)元组加入小顶堆heap\n",
    "# 第二步：取出堆顶元素（最小值），如果堆顶元素=上一次元素，则排名不变；否则，排名+1\n",
    "import heapq\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr):\n",
    "        heap = []\n",
    "        for i, x in enumerate(arr):\n",
    "            heapq.heappush(heap, (x, i))\n",
    "\n",
    "        rank = 0\n",
    "        last = None\n",
    "        while heap:\n",
    "            x, i = heapq.heappop(heap)\n",
    "            if x != last:\n",
    "                rank += 1\n",
    "            arr[i] = rank\n",
    "            last = x\n",
    "\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        m = dict()\n",
    "        for i,v in enumerate(arr):\n",
    "            m[v] = i\n",
    "        for j,v in enumerate(sorted(m.keys())):\n",
    "            m[v] = j+1\n",
    "        return list(map(lambda x:m[x] ,arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        m = dict()\n",
    "        for i,v in enumerate(arr):\n",
    "            m[v] = i\n",
    "        for j,v in enumerate(sorted(m.keys())):\n",
    "            m[v] = j+1\n",
    "        return [m[v] for v in arr]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        # 过滤掉重复的数字\n",
    "        numDict = {num:0 for num in arr}\n",
    "                 \n",
    "        # 备份 arr 中的数据\n",
    "        bakArr = arr[:]\n",
    "\n",
    "        # 将 arr 中的数据变成没有重复的数据\n",
    "        arr = sorted(list(numDict.keys()))\n",
    "\n",
    "        # 对 arr 中的数字进行位置编码                       \n",
    "        for i in range(len(arr)):           \n",
    "            numDict[arr[i]] = i+1\n",
    "        \n",
    "        # 返回数据\n",
    "        return [numDict[num] for num in bakArr]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        arr_dict = {}\n",
    "        arr_1 = sorted(arr)\n",
    "        p = 1\n",
    "        for i in arr_1:\n",
    "            if i not in arr_dict:\n",
    "                arr_dict[i]=p\n",
    "                p += 1\n",
    "        res = []\n",
    "        for i in arr:\n",
    "            res.append(arr_dict[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        pq = []\n",
    "        res = [-1] * len(arr)\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            heapq.heappush(pq, (arr[i], i))\n",
    "        \n",
    "\n",
    "        prev = -1000000001\n",
    "        prev_rank = 0\n",
    "\n",
    "        while pq:\n",
    "            val, idx = heapq.heappop(pq)\n",
    "            #print(val, idx, prev, prev_rank)\n",
    "\n",
    "            if val > prev:\n",
    "                prev_rank += 1\n",
    "                prev = val\n",
    "\n",
    "            res[idx] = prev_rank\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        newArr = arr.copy()\n",
    "        newArr.sort()\n",
    "        counter = 1\n",
    "        setArr = dict()\n",
    "        for a in newArr:\n",
    "            if a not in setArr:\n",
    "                setArr[a] = counter\n",
    "                counter += 1\n",
    "        return [setArr[i] for i in arr]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedSet\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\r\n",
    "        sset=SortedSet(arr);ans=[]\r\n",
    "        for i in arr:\r\n",
    "            ans.append(sset.index(i)+1)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        sarr = sorted(arr)\n",
    "        x2r = dict()\n",
    "        r = 1\n",
    "        for x in sarr:\n",
    "            if x not in x2r:\n",
    "                x2r[x] = r\n",
    "                r += 1\n",
    "        for i, x in enumerate(arr):\n",
    "            arr[i] = x2r[x]\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        dic={}\n",
    "        for i in arr:\n",
    "            if i not in dic:\n",
    "                dic[i]=1\n",
    "            else:\n",
    "                dic[i]+=1\n",
    "        likey=sorted(list(dic.keys()))\n",
    "        for i in range(0,len(likey)):\n",
    "            dic[likey[i]]=i+1\n",
    "        for j in range(0,len(arr)):\n",
    "            arr[j]=dic[arr[j]]\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        c = Counter(arr)\n",
    "        nums = sorted(list(c.keys()))\n",
    "        ans = []\n",
    "        for i in range(len(nums)):\n",
    "            c[nums[i]] = i + 1\n",
    "        for num in arr:\n",
    "            ans.append(c[num])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        if len(arr) == 0:\n",
    "            return []\n",
    "    \n",
    "        arr1 = list(sorted(arr))\n",
    "        location = dict()\n",
    "        cnt = 0\n",
    "        for i, num in enumerate(arr1):\n",
    "            if i == 0:\n",
    "                cnt += 1\n",
    "                location[num] = cnt\n",
    "            elif i > 0 and arr1[i] == arr1[i-1]:\n",
    "                continue\n",
    "            else:\n",
    "                cnt += 1\n",
    "                location[num] = cnt\n",
    "\n",
    "        res = []\n",
    "        for i, num in enumerate(arr):\n",
    "            ans = location[num]\n",
    "            res.append(ans)\n",
    "        return res\n",
    "\n",
    "            \n",
    "            \n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        def quick_sort(arr, start, end):\n",
    "            if start >= end:\n",
    "                return arr \n",
    "            pivot = arr[start]\n",
    "            i = start \n",
    "            j = end \n",
    "            while i < j:\n",
    "                while i < j and arr[j] >= pivot:\n",
    "                    j -= 1\n",
    "                # arr[j] < pivot\n",
    "                arr[i] = arr[j]\n",
    "                while i < j and arr[i] < pivot:\n",
    "                    i += 1\n",
    "                # arr[i] >= pivot\n",
    "                arr[j] = arr[i]\n",
    "            # i == j\n",
    "            arr[i] = pivot\n",
    "            quick_sort(arr, start=start, end=i - 1)\n",
    "            quick_sort(arr, start=i + 1, end=end)\n",
    "            return arr\n",
    "        arr_cp = deepcopy(arr)\n",
    "        quick_sort(arr_cp, start = 0, end = len(arr) - 1)\n",
    "        # print(\"after sorted, arr:\", arr_cp)\n",
    "        hash_map = {}\n",
    "        index = 0\n",
    "        for i in range(len(arr_cp)):\n",
    "            if arr_cp[i] not in hash_map:\n",
    "                hash_map[arr_cp[i]] = index + 1\n",
    "                index += 1\n",
    "        res = []\n",
    "        for i in range(len(arr)):\n",
    "            res.append(hash_map[arr[i]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        hashmap=collections.defaultdict(int)\n",
    "        hp=list()\n",
    "        ans=list()\n",
    "        for nu in arr:\n",
    "            heapq.heappush(hp,nu)\n",
    "        n=len(hp)\n",
    "        i=0\n",
    "        for k in range(n):\n",
    "            curr=heapq.heappop(hp)\n",
    "            if curr not in hashmap:\n",
    "                hashmap[curr]=i\n",
    "                i=i+1\n",
    "        for num in arr:\n",
    "            ans.append(hashmap[num]+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        if arr == []:\n",
    "            return arr\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            arr[i] = [arr[i],i]\n",
    "        arr.sort(key=lambda x:x[0])\n",
    "        #print(arr)\n",
    "        k = 1\n",
    "        s=arr[0][0]\n",
    "        arr[0][0] = 1\n",
    "        i=1\n",
    "        while i<n:\n",
    "            if arr[i][0]==s:\n",
    "                while i<n and arr[i][0]==s:\n",
    "                    arr[i][0] = k\n",
    "                    i+=1\n",
    "                    #print(i)\n",
    "                i-=1\n",
    "            else:\n",
    "                k+=1\n",
    "                s = arr[i][0]\n",
    "                arr[i][0] = k\n",
    "                #print(k,s,arr[i][0],i)\n",
    "            i+=1\n",
    "        arr.sort(key=lambda x:x[1])\n",
    "        #print(arr)\n",
    "        for i in range(n):\n",
    "            arr[i]=(arr[i][0])\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        c=copy.deepcopy(arr)\n",
    "        arr.sort()\n",
    "        dict ={}\n",
    "        print(arr)\n",
    "        count =0\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] not in dict:\n",
    "                dict[arr[i]] = i+1-count\n",
    "            else:\n",
    "                count = count+1\n",
    "        print(dict)\n",
    "        return [dict[item] for item in c]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        arr_1 = sorted(arr)\n",
    "        pos = {}\n",
    "        double_count =0\n",
    "        for i,num in enumerate(arr_1):\n",
    "            if num in pos:\n",
    "                double_count +=1\n",
    "                continue\n",
    "            pos[num] = i - double_count \n",
    "        return [pos[num]+1 for num in arr]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        ranks = {v: i for i, v in enumerate(sorted(set(arr)), 1)}\n",
    "        return [ranks[v] for v in arr]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        t=sorted(set(arr))\n",
    "        d={}\n",
    "        for i,v in enumerate(t,1):\n",
    "           d[v]=i\n",
    "        return [d[v] for v in arr]\n",
    "      \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        x2r = dict()\n",
    "        for i, x in enumerate(sorted(set(arr))):\n",
    "            x2r[x] = i + 1\n",
    "        for i, x in enumerate(arr):\n",
    "            arr[i] = x2r[x]\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        rank={v:i for i,v in enumerate(sorted(list(set(arr))),1)}\n",
    "        return [rank[x] for x in arr]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        a = arr.copy()\n",
    "        a = sorted(set(arr))\n",
    "        rank = enumerate(a,1)\n",
    "        d = {}\n",
    "        for i,j in rank:\n",
    "            d[j] = i\n",
    "        return [d[i] for i in arr]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        arr2 = arr.copy()\n",
    "\n",
    "        arr2 = list(set(arr2))\n",
    "        arr2.sort()\n",
    "\n",
    "        d = {}\n",
    "        for i in range(len(arr2)):\n",
    "            if arr2[i] not in d.keys():\n",
    "                d[arr2[i]] = i + 1\n",
    "\n",
    "        result = []\n",
    "        for i in range(len(arr)):\n",
    "            result.append(d[arr[i]])\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self,arr):\n",
    "        index = {}\n",
    "        k=1\n",
    "        new = [i for i in arr]\n",
    "        arr.sort()\n",
    "        for i in arr:\n",
    "            if i not in index:\n",
    "                index[i] = k\n",
    "                k+=1\n",
    "        ans = []\n",
    "        for j in new:\n",
    "            ans.append(index[j])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        arr2=arr[:]\n",
    "        h={}\n",
    "        arr2.sort()\n",
    "        i=1\n",
    "        for  a in arr2:\n",
    "            if a not in h:\n",
    "                h[a]=i\n",
    "                i+=1\n",
    "        for j,num in enumerate(arr):\n",
    "            arr[j]=h[num]\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        dic = {}\n",
    "        for i in sorted(arr):\n",
    "            if i not in dic:\n",
    "                dic[i] = len(dic) + 1\n",
    "        return [dic[i] for i in arr]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        # a=[i for i in arr]\n",
    "        # a.sort()\n",
    "        # b=0\n",
    "        # c=0\n",
    "        \n",
    "        # for i in range(len(arr)):\n",
    "            \n",
    "            \n",
    "        #     arr[i]=a.index(arr[i])+1-b+c\n",
    "        #     if i<len(arr)-1 and a[i]==a[i+1]:\n",
    "        #         b=b+1\n",
    "        #         c=c+1\n",
    "        #     else:\n",
    "        #         c=0\n",
    "\n",
    "        # return arr\n",
    "        \n",
    "        # a=[i for i in arr]\n",
    "        \n",
    "        # a.sort()\n",
    "        # d={}\n",
    "        # b=0\n",
    "        # c=0\n",
    "        \n",
    "        # for i in range(len(arr)):\n",
    "            \n",
    "            \n",
    "        #     d[a[i]]=a.index(a[i])+1-b+c\n",
    "        #     if i<len(arr)-1 and a[i]==a[i+1]:\n",
    "        #         b=b+1\n",
    "        #         c=c+1\n",
    "        #     else:\n",
    "        #         c=0\n",
    "        \n",
    "        # for i in range(len(arr)):\n",
    "        #     arr[i]=d[arr[i]]\n",
    "\n",
    "        # return arr\n",
    "\n",
    "        a={}\n",
    "        \n",
    "        \n",
    "        \n",
    "        for i,j in enumerate(sorted(set(arr))) :\n",
    "            \n",
    "            a[j]=i+1\n",
    "        \n",
    "            \n",
    "        \n",
    "        for i in range(len(arr)):\n",
    "            arr[i]=a[arr[i]]\n",
    "\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        a = sorted(set(arr))\n",
    "        d = {}\n",
    "        for i, v in enumerate(a, 1):\n",
    "            d[v] = i\n",
    "        return [d[i] for i in arr]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        a=sorted(set(arr))\n",
    "        d={}\n",
    "        for k,v in enumerate(a,1):\n",
    "            d[v]=k\n",
    "        return [d[i] for i in arr]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        hashmap={}\n",
    "        L=sorted(list(set(arr)))\n",
    "        for i,element in enumerate(L):\n",
    "            hashmap[element]=i+1\n",
    "        return [hashmap[i] for i in arr]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        if len(arr) ==1:\n",
    "            return [1]\n",
    "        if not arr:\n",
    "            return []\n",
    "        new_arr = sorted(list(set(arr)))\n",
    "        dic = {}\n",
    "        for i,num in enumerate(new_arr):\n",
    "            if num not in dic.keys():\n",
    "                dic[num] = i+1\n",
    "        result = []\n",
    "        for i in arr:\n",
    "            result.append(dic[i])\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        hash_T = {}\n",
    "        cnt = 0\n",
    "        for num in sorted(arr):\n",
    "            if num not in hash_T:\n",
    "                cnt += 1\n",
    "                hash_T[num] = cnt\n",
    "        return [hash_T[i] for i in arr]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        tmpArr = arr[:]\n",
    "        tmpArr.sort()\n",
    "        rankDict = {}\n",
    "        \n",
    "        for num in tmpArr:\n",
    "            if num not in rankDict:\n",
    "                rankDict[num] = len(rankDict) + 1\n",
    "        \n",
    "        ranks = []\n",
    "        for num in arr:\n",
    "            ranks.append(rankDict[num])\n",
    "        \n",
    "        return ranks\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        t = sorted(arr)\n",
    "        d = dict()\n",
    "        i = 1\n",
    "        for x in t:\n",
    "            if x not in d:\n",
    "                d[x] = i\n",
    "                i += 1\n",
    "        ans = []\n",
    "        for x in arr:\n",
    "            ans.append(d[x])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        sort_arr = sorted(set(arr))\n",
    "        res = {}\n",
    "        for index,val in enumerate(sort_arr):\n",
    "            res.setdefault(val,index+1)\n",
    "        data = [res[val] for val in arr]\n",
    "        return data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        order = {x : i + 1 for i, x in enumerate(sorted(set(arr)))}\n",
    "        return [order[x] for x in arr]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        ranks = {v: i for i, v in enumerate(sorted(set(arr)), 1)}\n",
    "        return [ranks[v] for v in arr]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        s = set(arr)\n",
    "        s = sorted(list(s))\n",
    "        dic = dict()\n",
    "        for i, v in enumerate(s, 1):\n",
    "            dic[v] = i\n",
    "        return [dic[v] for v in arr]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        # 有相同元素的离散化\n",
    "        n = len(arr)\n",
    "        if n == 0:\n",
    "            return []\n",
    "\n",
    "        rank = sorted(zip(arr, range(n)))\n",
    "        id = 1\n",
    "        arr[rank[0][1]] = 1\n",
    "        last = rank[0][0]\n",
    "        for n, i in rank[1:]:\n",
    "            if n != last:\n",
    "                id += 1\n",
    "                last = n\n",
    "            arr[i] = id\n",
    "        return arr\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        arr1 = sorted(arr)\n",
    "        b = []\n",
    "        my_dict = {value: index for index, value in enumerate(sorted(set(arr1)), start=1)}\n",
    "        for i in arr:\n",
    "            b.append(my_dict[i])\n",
    "        return b \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "\n",
    "        # 哈希\n",
    "        L = arr[:]\n",
    "        table = {v:i for i, v in enumerate(sorted(set(L)), 1)}\n",
    "        print(table)\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            arr[i] = table[arr[i]]\n",
    "        return arr\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        set_arr = list(set(arr))\n",
    "        sorted_arr = sorted(set_arr)\n",
    "        dict1 = {}\n",
    "        for i in range(len(sorted_arr)):\n",
    "            dict1[sorted_arr[i]] = i+1\n",
    "        temp_list =[]\n",
    "        for i in arr:\n",
    "            temp_list.append(dict1[i])\n",
    "        return temp_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "            arr_ascending = list(set(arr))\n",
    "            arr_ascending.sort()\n",
    "            Hash = {}\n",
    "            result = [0 for i in range(len(arr))]\n",
    "            for j,k in enumerate(arr_ascending):\n",
    "                Hash[k] = j+1\n",
    "            for l in range(len(arr)):\n",
    "                result[l] = Hash[arr[l]]\n",
    "            return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        res = sorted(enumerate(arr),key=lambda x:x[1])\n",
    "        no = 1\n",
    "        i = 0\n",
    "        while i < len(res):\n",
    "            if i > 0 and res[i][1] > res[i-1][1]:\n",
    "                no += 1\n",
    "            arr[res[i][0]] = no\n",
    "            i += 1\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        print(sorted(set(arr)))\n",
    "        dct = {num: i+1 for i, num in enumerate(sorted(set(arr)))}\n",
    "        return [dct[num] for num in arr]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        if n == 0: return []\n",
    "        ans = [0] * n\n",
    "        temp = [(v, i) for i, v in enumerate(arr)]\n",
    "        temp.sort()\n",
    "        rank = 1\n",
    "        ans[temp[0][1]] = 1\n",
    "        for i in range(1, n):\n",
    "            if temp[i][0] != temp[i - 1][0]:\n",
    "                rank += 1\n",
    "            ans[temp[i][1]] = rank\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        tmp = set(arr)\n",
    "        tmp = sorted(list(tmp))\n",
    "        dic = {}\n",
    "        for i, j in enumerate(tmp):\n",
    "            dic[j] = i\n",
    "        ans = []\n",
    "        for i in arr:\n",
    "            ans.append(dic[i] + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        lis = set(arr)\n",
    "        dicti = dict(zip(sorted(lis),range(1,len(lis)+1)))\n",
    "        res = [dicti[arr[i]] for i in range(len(arr)) ]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        ans = [0] * n\n",
    "        ll = list(zip(arr, range(n)))\n",
    "        ll.sort(key=lambda x: x[0])\n",
    "        r = 1\n",
    "        for i, x in enumerate(ll):\n",
    "            # print(i, x)\n",
    "            if i == 0:\n",
    "                ans[x[1]] = r\n",
    "                r += 1\n",
    "            else:\n",
    "                if x[0] == ll[i - 1][0]:\n",
    "                    ans[x[1]] = ans[ll[i - 1][1]]\n",
    "                else:\n",
    "                    ans[x[1]] = r\n",
    "                    r += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        asl = list(set(arr))\n",
    "        asl.sort()\n",
    "        ad = dict()\n",
    "        for i in range(len(asl)):\n",
    "            ad[asl[i]] = i\n",
    "        \n",
    "        for i in range(len(arr)):\n",
    "            arr[i] = ad[arr[i]] + 1\n",
    "        \n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        ranks = {v: i for i, v in enumerate(sorted(set(arr)))}\n",
    "        return [ranks[i]+1 for i in arr]\n",
    "        # d1 = [[key, val] for val, key in enumerate(arr)]\n",
    "        # d1.sort()\n",
    "        # k = 0\n",
    "        # pre = 0\n",
    "        # for i in range(len(d1)):\n",
    "        #     if d1[i][0] == pre:\n",
    "        #         k += 1\n",
    "        #     pre = d1[i][0]\n",
    "        #     # d1[i][0] = i + 1 - k\n",
    "        #     d1[i][0] = d1[i][1]\n",
    "        #     d1[i][1] = i - k + 1\n",
    "        # d1.sort()\n",
    "        # return [d1[i][1] for i in range(len(d1))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        nums=set(arr)\n",
    "        nums=sorted(nums)\n",
    "        ans=[]\n",
    "        count={ch:i for i,ch in enumerate(nums)}\n",
    "        for x in arr:\n",
    "            ans.append(count[x]+1)\n",
    "        return ans\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "       \n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        nums = sorted(list(set(arr)))\n",
    "        dictnum = {}\n",
    "        for i in range(len(nums)):\n",
    "            dictnum[nums[i]] = i\n",
    "        res = []\n",
    "        for a in arr:\n",
    "            res.append(dictnum[a]+1)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        s=set(arr)\n",
    "        l=list(s)\n",
    "        l.sort()\n",
    "        d={}\n",
    "        for i,k in enumerate(l):\n",
    "            d[k]=i\n",
    "        for i in range(len(arr)):\n",
    "            arr[i]=d[arr[i]]+1\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        newarr = collections.Counter(sorted(arr))\n",
    "        dictarr = {}\n",
    "        for i, x in enumerate(newarr.keys()) :\n",
    "            dictarr[x] = i+1\n",
    "\n",
    "        for i in range(0,len(arr)):\n",
    "            arr[i] = dictarr[arr[i]]\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        if not arr:\n",
    "            return []\n",
    "        n=len(arr)\n",
    "        directiron=[[arr[i],i] for i in range(n)]\n",
    "        directiron.sort( key=(lambda x:x[0]) )\n",
    "        res=[1]*n\n",
    "        pre=directiron[0][0]\n",
    "        preRes=1\n",
    "        for i in range(n):\n",
    "            if directiron[i][0]==pre:\n",
    "                res[directiron[i][1]]=preRes\n",
    "            else:\n",
    "                preRes+=1\n",
    "                res[directiron[i][1]]=preRes\n",
    "                pre=directiron[i][0]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        tmp = set(arr)\n",
    "        tmp = sorted(tmp)\n",
    "        rank = {v:r for r,v in enumerate(tmp)}\n",
    "        for i in range(len(arr)):\n",
    "            arr[i]=rank[arr[i]]+1\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        t=list(set([x for x in arr]))\n",
    "        t.sort()\n",
    "        ad={v:k for k,v in enumerate(t)}\n",
    "        #print(ad)\n",
    "        for i in range(len(arr)):\n",
    "            arr[i]=ad[arr[i]]+1\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        dic = {val: idx for idx, val in enumerate(sorted(set(arr)))}\n",
    "        return [dic[val] + 1 for val in arr]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        dic = {val: idx for idx, val in enumerate(sorted(set(arr)))}\n",
    "        return [dic[val] + 1 for val in arr]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        pos_dict = {v:k for k, v in enumerate(sorted(list(set(arr))))}\n",
    "        return [pos_dict.get(v) + 1 for v in arr]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        dict1={}\n",
    "        aa=sorted(list(set(arr)))\n",
    "        for i in range(len(aa)):\n",
    "            if aa[i] not in dict1:\n",
    "                dict1[aa[i]]=i \n",
    "        return [dict1[i]+1 for i in arr]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayRankTransform(self, arr: List[int]) -> List[int]:\n",
    "        appearSet = set()\n",
    "        for num in arr:\n",
    "            appearSet.add(num)\n",
    "        sortlist = list(appearSet)\n",
    "        sortlist.sort()\n",
    "        num2idx = {}\n",
    "        for i, num in enumerate(sortlist):\n",
    "            num2idx[num] = i + 1\n",
    "        ans = []\n",
    "        for num in arr:\n",
    "            ans.append(num2idx[num])\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
